home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / a_utils / _archvrs / unix / lha101u.lha / lha / src / dhuf.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-24  |  5.4 KB  |  308 lines
  1. /**************************************************************
  2.     title   dhuf.c
  3. ***************************************************************
  4.     Dynamic Huffman routine
  5.                                                 H.Yoshizaki
  6. **************************************************************/
  7. #include <stdio.h>
  8. #include "slidehuf.h"
  9.  
  10. #define N_CHAR      (256 + 60 - THRESHOLD + 1)
  11. #define TREESIZE_C  (N_CHAR * 2)
  12. #define TREESIZE_P  (128 * 2)
  13. #define TREESIZE    (TREESIZE_C + TREESIZE_P)
  14. #define ROOT_C      0
  15. #define ROOT_P      TREESIZE_C
  16.  
  17. unsigned int n_max;
  18.  
  19. static short child [TREESIZE],
  20.              parent[TREESIZE],
  21.              block [TREESIZE],
  22.              edge  [TREESIZE],
  23.              stock [TREESIZE],
  24.              node  [TREESIZE / 2];
  25.  
  26. static unsigned short freq[TREESIZE];
  27.  
  28. static unsigned short total_p;
  29. static int avail, n1;
  30. static int most_p, nn;
  31. static unsigned long nextcount;
  32.  
  33. void start_c_dyn(void)
  34. {
  35.     int i, j, f;
  36.  
  37.     n1 = (n_max >= 256 + maxmatch - THRESHOLD + 1) ? 512 : n_max - 1;
  38.     for (i = 0; i < TREESIZE_C; i++) {
  39.         stock[i] = i;
  40.         block[i] = 0;
  41.     }
  42.     for (i = 0, j = n_max * 2 - 2; i < n_max; i++, j--) {
  43.         freq[j] = 1;
  44.         child[j] = ~i;
  45.         node[i] = j;
  46.         block[j] = 1;
  47.     }
  48.     avail = 2;
  49.     edge[1] = n_max - 1;
  50.     i = n_max * 2 - 2;
  51.     while (j >= 0) {
  52.         f = freq[j] = freq[i] + freq[i - 1];
  53.         child[j] = i;
  54.         parent[i] = parent[i - 1] = j;
  55.         if (f == freq[j + 1]) {
  56.             edge[block[j] = block[j + 1]] = j;
  57.         } else {
  58.             edge[block[j] = stock[avail++]] = j;
  59.         }
  60.         i -= 2;
  61.         j--;
  62.     }
  63. }
  64.  
  65. static void start_p_dyn(void)
  66. {
  67.     freq[ROOT_P] = 1;
  68.     child[ROOT_P] = ~(N_CHAR);
  69.     node[N_CHAR] = ROOT_P;
  70.     edge[block[ROOT_P] = stock[avail++]] = ROOT_P;
  71.     most_p = ROOT_P;
  72.     total_p = 0;
  73.     nn = 1 << dicbit;
  74.     nextcount = 64;
  75. }
  76.  
  77. void decode_start_dyn(void)
  78. {
  79.     n_max = 286;
  80.     maxmatch = MAXMATCH;
  81.     init_getbits();
  82.     start_c_dyn();
  83.     start_p_dyn();
  84. }
  85.  
  86. static void reconst( start , end )
  87. int start;
  88. int end;
  89. {
  90.     int i, j, k, l, b;
  91.     unsigned int f, g;
  92.  
  93.     for (i = j = start; i < end; i++) {
  94.         if ((k = child[i]) < 0) {
  95.             freq[j] = (freq[i] + 1) / 2;
  96.             child[j] = k;
  97.             j++;
  98.         }
  99.         if (edge[b = block[i]] == i) {
  100.             stock[--avail] = b;
  101.         }
  102.     }
  103.     j--;
  104.     i = end - 1;
  105.     l = end - 2;
  106.     while (i >= start) {
  107.         while (i >= l) {
  108.             freq[i] = freq[j]; child[i] = child[j];
  109.             i--, j--;
  110.         }
  111.         f = freq[l] + freq[l + 1];
  112.         for (k = start; f < freq[k]; k++);
  113.         while(j >= k) {
  114.             freq[i] = freq[j]; child[i] = child[j];
  115.             i--, j--;
  116.         }
  117.         freq[i] = f; child[i] = l + 1;
  118.         i--;
  119.         l -= 2;
  120.     }
  121.     f = 0;
  122.     for (i = start; i < end; i++) {
  123.         if ((j = child[i]) < 0) node[~j] = i;
  124.         else parent[j] = parent[j - 1] = i;
  125.         if ((g = freq[i]) == f) {
  126.             block[i] = b;
  127.         } else {
  128.             edge[b = block[i] = stock[avail++]] = i;
  129.             f = g;
  130.         }
  131.     }
  132. }
  133.  
  134. static int swap_inc(p)
  135. int p;
  136. {
  137.     int b, q, r, s;
  138.  
  139.     b = block[p];
  140.     if ((q = edge[b]) != p) {    /* swap for leader */
  141.         r = child[p]; s = child[q];
  142.         child[p] = s; child[q] = r;
  143.         if (r >= 0) parent[r] = parent[r - 1] = q;
  144.         else        node[~r] = q;
  145.         if (s >= 0)    parent[s] = parent[s - 1] = p;
  146.         else        node[~s] = p;
  147.         p = q;
  148.         goto Adjust;
  149.     } else if (b == block[p + 1]) {
  150. Adjust:
  151.         edge[b]++;
  152.         if (++freq[p] == freq[p - 1]) {
  153.             block[p] = block[p - 1];
  154.         } else {
  155.             edge[block[p] = stock[avail++]] = p;    /* create block */
  156.         }
  157.     } else if (++freq[p] == freq[p - 1]) {
  158.         stock[--avail] = b;        /* delete block */
  159.         block[p] = block[p - 1];
  160.     }
  161.     return parent[p];
  162. }
  163.  
  164. static void update_c(p)
  165. int p;
  166. {
  167.     int q;
  168.  
  169.     if (freq[ROOT_C] == 0x8000) {
  170.         reconst(0, n_max * 2 - 1);
  171.     }
  172.     freq[ROOT_C]++;
  173.     q = node[p];
  174.     do {
  175.         q = swap_inc(q);
  176.     } while (q != ROOT_C);
  177. }
  178.  
  179. static void update_p(p)
  180. int p;
  181. {
  182.     int q;
  183.  
  184.     if (total_p == 0x8000) {
  185.         reconst(ROOT_P, most_p + 1);
  186.         total_p = freq[ROOT_P];
  187.         freq[ROOT_P] = 0xffff;
  188.     }
  189.     q = node[p + N_CHAR];
  190.     while (q != ROOT_P) {
  191.         q = swap_inc(q);
  192.     }
  193.     total_p++;
  194. }
  195.  
  196. static void make_new_node(p)
  197. int p;
  198. {
  199.     int q, r;
  200.  
  201.     r = most_p + 1; q = r + 1;
  202.     node[~(child[r] = child[most_p])] = r;
  203.     child[q] = ~(p + N_CHAR);
  204.     child[most_p] = q;
  205.     freq[r] = freq[most_p];
  206.     freq[q] = 0;
  207.     block[r] = block[most_p];
  208.     if (most_p == ROOT_P) {
  209.         freq[ROOT_P] = 0xffff;
  210.         edge[block[ROOT_P]]++;
  211.     }
  212.     parent[r] = parent[q] = most_p;
  213.     edge[block[q] = stock[avail++]] = node[p + N_CHAR] = most_p = q;
  214.     update_p(p);
  215. }
  216.  
  217. static void encode_c_dyn(c)
  218. int c;
  219. {
  220.     unsigned int bits;
  221.     int p, d, cnt;
  222.  
  223.     d = c - n1;
  224.     if (d >= 0) {
  225.         c = n1;
  226.     }
  227.     cnt = bits = 0;  
  228.     p = node[c];
  229.     do {
  230.         bits >>= 1;
  231.         if (p & 1) {
  232.             bits |= 0x8000;
  233.         }
  234.         if (++cnt == 16) {
  235.             putcode(16, bits);
  236.             cnt = bits = 0;
  237.         }
  238.     } while ((p = parent[p]) != ROOT_C);
  239.     putcode(cnt, bits);
  240.     if (d >= 0) putbits(8, d);
  241.     update_c(c);
  242. }
  243.  
  244. unsigned short decode_c_dyn(void)
  245. {
  246.     int c;
  247.     short buf, cnt;
  248.  
  249.     c = child[ROOT_C];
  250.     buf = bitbuf;
  251.     cnt = 0;
  252.     do {
  253.         c = child[c - (buf < 0)];
  254.         buf <<= 1;
  255.         if (++cnt == 16) {
  256.             fillbuf(16);
  257.             buf = bitbuf; cnt = 0;
  258.         }
  259.     } while (c > 0);
  260.     fillbuf(cnt);
  261.     c = ~c;
  262.     update_c(c);
  263.     if (c == n1) c += getbits(8);
  264.     return c;
  265. }
  266.  
  267. unsigned short decode_p_dyn(void)
  268. {
  269.     int c;
  270.     short buf, cnt;
  271.  
  272.     while (count > nextcount) {
  273.         make_new_node(nextcount / 64);
  274.         if ((nextcount += 64) >= nn)
  275.             nextcount = 0xffffffff;
  276.     }
  277.     c = child[ROOT_P];
  278.     buf = bitbuf; cnt = 0;
  279.     while (c > 0) {
  280.         c = child[c - (buf < 0)];
  281.         buf <<= 1;
  282.         if (++cnt == 16) {
  283.             fillbuf(16);
  284.             buf = bitbuf; cnt = 0;
  285.         }
  286.     }
  287.     fillbuf(cnt);
  288.     c = (~c) - N_CHAR;
  289.     update_p(c);
  290.  
  291.     return (c << 6) + getbits(6);
  292. }
  293.  
  294. void output_dyn( code , pos )
  295. int code;
  296. unsigned int pos;
  297. {
  298.     encode_c_dyn(code);
  299.     if (code >= 0x100) {
  300.         encode_p_st0(pos);
  301.     }
  302. }
  303.  
  304. void encode_end_dyn(void)
  305. {
  306.     putcode(7, 0);
  307. }
  308.